/*
 * Created by guoyh on Sun Dec 04 2022 22:08:11
 * leetcode NO.40 https://leetcode.cn/problems/combination-sum-ii/
 */

#include <iostream>
#include <gtest/gtest.h>
#include<vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> path;
        vector<int> visited;
        int size = candidates.size();
        visited.resize(size);
        sort(candidates.begin(), candidates.end());
        backtrack(res, path, candidates, 0, visited, target);
        return res;
    }

    void backtrack(vector<vector<int>>& res, vector<int>& path, vector<int>& candidates, int index, vector<int>& visited, int target){
        // cout<<"index="<<index<<" target="<<target<<endl;
        if(target < 0){
            return;
        }
        if(target == 0){
            res.push_back(path);
            return;
        }

        for(int i = index; i < candidates.size(); i++){
            // cout<<"i="<<i<<" index="<<index<<endl;
            // 剪枝
            if(i > 0 && candidates[i] == candidates[i-1] && !visited[i-1]){
                continue;
            }

            visited[i] = 1;
            path.push_back(candidates[i]);

            backtrack(res, path, candidates, i + 1, visited, target - candidates[i]);

            visited[i] = 0;
            path.pop_back();
        }

    }
};

TEST(MyTest, AddTest) {
    Solution slu;
    vector<int> candidates = {2,5,2,1,2};
    vector<vector<int>> res = slu.combinationSum2(candidates, 5);

    ASSERT_EQ(res.size(), 2);

}
TEST(MyTest, AddTest1) {
    Solution slu;
    vector<int> candidates = {10,1,2,7,6,1,5};
    vector<vector<int>> res = slu.combinationSum2(candidates, 8);

    ASSERT_EQ(res.size(), 4);

}

TEST(MyTest, AddTest2) {
    Solution slu;
    vector<int> candidates = {2,5,2,1,2};
    vector<vector<int>> res = slu.combinationSum2(candidates, 6);

    ASSERT_EQ(res.size(), 2);

}

TEST(MyTest, AddTest3) {
    Solution slu;
    vector<int> candidates = {2,5,2,1,2,9,4,7};
    vector<vector<int>> res = slu.combinationSum2(candidates, 7);

    ASSERT_EQ(res.size(), 4);

}

int main(int argc, char *argv[]) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}

